package leetcode.code600;

public class Solution extends Solution600 {

	private final char ZERO = '0';
	private final char ONE = '1';

	@Override
	public int findIntegers(int n) {
		String str = Integer.toBinaryString(n);
		char[] max = str.toCharArray();
		char[] chars = new char[str.length()];
		int ans = this.findIntegers(0, -1, chars, max, true);
		return ans;
	}

	private int findIntegers(int index, int lastIndex, char[] chars, char[] max, boolean lastMatchMax) {
		if (index == chars.length) {
			return 1;
		}
		int ans = 0;
		chars[index] = ZERO;
		boolean indexMatch = lastMatchMax ? chars[index] == max[index] : false;
		ans += findIntegers(index + 1, index, chars, max, indexMatch);
		if (lastIndex == -1 || (!lastMatchMax && chars[lastIndex] == ZERO)
				|| (lastMatchMax && chars[lastIndex] == ZERO && max[index] == ONE)) {
			chars[index] = ONE;
			indexMatch = lastMatchMax ? chars[index] == max[index] : false;
			ans += findIntegers(index + 1, index, chars, max, indexMatch);
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();

		for(int i=0;i<11;i++) {
			int r = so.findIntegers(i);
			System.out.println(i + " " +r);
		}

	}

}
